package org.basis.algorithm.doublepointer;

import java.util.HashMap;
import java.util.Map;

/**
 * 滑动窗口算法解题模板
 *
 * @author wenpan 2024/03/02 14:38
 */
public class SlidingWindow {

    public static void main(String[] args) {
        final String str = "ADOBECODEBANC";
        System.out.println(str.substring(0, 5));

        final String s = "aa";
        final String t = "aa";
        String s1 = process1(s, t);
        System.out.println(s1);
    }

    /**
     * 使用滑动窗口模板来解题
     */
    public static String process1(String s, String t) {
        // 特例判定
        if (s == null || t == null || s.length() < t.length()) {
            return "";
        }
        Map<Character, Integer> need = new HashMap<>();
        Map<Character, Integer> window = new HashMap<>();
        char[] targetChars = t.toCharArray();
        // 将目标字符串拆解到map中(初始化)
        for (int i = 0; i < targetChars.length; i++) {
            char c = targetChars[i];
            Integer count = need.getOrDefault(c, 0);
            // 注意这里应该是++count，不能是count++，因为count++表示执行了put后再进行加一操作
            need.put(c, ++count);
        }

        char[] chars = s.toCharArray();
        int left = 0;
        int right = 0;
        int valid = 0;
        // 最小覆盖子串的起始位置
        int start = 0;
        // 要截取的长度
        int len = Integer.MAX_VALUE;

        while (right < chars.length) {
            // 即将进入窗口的字符
            char c = chars[right];
            // 窗口右移
            right++;
            // 判定、更新
            int count = window.getOrDefault(c, 0);

            // 该字符是需要的目标字符
            if (need.get(c) != null) {
                // 将字符c移入窗口，也就是在窗口内出现的次数 +1，注意在Java中这里不能是count++，因为count++表示执行完put后再加一
                window.put(c, ++count);
                // 窗口内部的c这个字符的数量已经和need的相同了，则表示匹配了一个有效字符了
                if (window.get(c).equals(need.get(c))) {
                    valid++;
                }
            }

            // 判断左窗口是否要收缩，当相等时说明窗口内已经有字符串t的全部字符了
            while (valid == need.size()) {
                // 如果窗口内已经有字符串t的全部字符了，则子串的起始位置就是left指针所在位置
                // 如果左右边界间的距离比之前得到的len还要小，那么就要进行更新了
                if (right - left < len) {
                    start = left;
                    // 长度就等于右边界 - 左边界
                    len = right - left;
                }
                // d 是即将移出窗口的元素
                char d = chars[left];
                // 窗口左边界右移（收缩）
                left++;
                // 进行窗口内的数据一系列更新
                // 如果需要移出窗口的d字符存在于need内才进行处理（也就是是t字符串的字符），否则不处理，继续移出下一个字符
                if (need.get(d) != null) {
                    // 获取d字符再window内出现的次数
                    int num = window.get(d);
                    // 该元素在窗口内出现的次数和在need中出现的次数相同（因为d马上就要被移出窗口，移出前出现次数相等，那么移出后次数就不相等了，所以valid要减一）
                    if (num == need.get(d)) {
                        // 该元素被移出窗口后，有效匹配的字符个数减一
                        valid--;
                    }
                    // 窗口内d字符出现的次数减一，注意这里是--num，不能是num--，num--表示先自行put后再减一
                    window.put(d, --num);
                }
            }
        }

        // 返回结果，这里注意一下Java中的substring方法，都是小写，第一个参数表示起始位置，第二参数表示结束位置(有点小坑)
        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
    }

    /**
     * 滑动窗口解题模板，遇到滑动窗口的问题可以直接套用该模板，或者基于该模板修改下即可
     */
    public static void template(String str, String t) {
        // 变为数组
        char[] chars = str.toCharArray();
        // 记录目标需要
        Map<Character, Integer> need = new HashMap<>();
        // 窗口
        Map<Character, Integer> window = new HashMap<>();

        // 左指针
        int left = 0;
        // 右指针
        int right = 0;
        // 是否已经满足条件
        final int valid = 0;

        while (right < chars.length) {
            // 即将要移入窗口的字符
            char c = chars[right];
            // 窗口右移
            right++;
            // 进行窗口内数据的一系列更新
            // ............

            // debug 打印
            System.out.println("窗口左边界：" + left + "，窗口右边界：" + right);

            // 这里你会发现两个while里的右移窗口和左移窗口的操作完全对称

            // 判断左侧窗口是否要收缩
            while (1 == 1) {
                // d是将要移出窗口的字符
                char d = chars[left];
                left++;
                // 进行窗口内数据的一系列更新
                // ..........
            }

        }
    }

}
